package com.lisp.algorithm.leetcode;

public class MedianOf2SortedArray {

	public static void main(String[] args) {
		int a[] = {1, 2, 3};
		int b[] = {2, 3};
		System.out.println(median2(a, b));
	}
	
	private static double median(int a[], int b[]) {
		int totalLen = a.length + b.length;
		if(totalLen % 2 == 0) {
			int k1 = totalLen/2;
			int k2 = k1+1;
			int k1Value = median(a, 0, b, 0, k1);
			int k2Value = median(a, 0, b, 0, k2);
			return (k1Value + k2Value) / 2.0;
		} else {
			int k = totalLen/2 + 1;
			return median(a, 0, b, 0, k);
		}
	}
	
	private static int median(int a[], int aStart, int b[], int bStart, int k) {
		if(aStart >= a.length) {
			return b[bStart + k - 1];
		} else if(bStart >= b.length) {
			return a[aStart + k-1];
		}
		
		if(k == 1) {
			return Math.min(a[aStart], b[bStart]);
		} else {
			int halfK = k/2;
			int aHalfKIndex = aStart + halfK-1;
			int aIndex = Math.min(aHalfKIndex, a.length-1);
			
			int bHalfKIndex = bStart + halfK-1;
			int bIndex = Math.min(bHalfKIndex, b.length - 1);
			
			if(a[aIndex] <= b[bIndex]) {
				return median(a, aIndex+1, b, bStart, k-(aIndex+1-aStart));
			} else {
				return median(a, aStart, b, bIndex+1, k - (bIndex+1-bStart));
			}
		}
	}

	private static double median2(int a[], int b[]) {
		int m = a.length, n = b.length;
		int ith = findIth(a, 0, m, b);
		int jth = (m+n+1)/2 - ith;
		
		if((m + n) % 2 == 0) {
			int prevMax = Math.max(read(a, ith-1), read(b, jth-1));
			int postMin = Math.min(read(a, ith), read(b, jth));
			return (prevMax + postMin) / 2.0;
		} else {
			return Math.max(read(a, ith-1), read(b, jth-1));
		}
	}
	
	private static int findIth(int a[], int aStart, int aEnd, int b[]) {
		int m = a.length, n = b.length;
		int ith=(aStart + aEnd) / 2;
		int jth = (m+n+1)/2 - ith;
		
		if(read(a, ith-1) <= read(b, jth)) {
			if(read(a, ith) > read(b, jth-1)) {
				return ith;
			} else {
				return findIth(a, ith+1, aEnd, b);
			}
		} else {
			return findIth(a, aStart, ith-1, b);
		}
	}
	
	private static int read(int a[], int i) {
		if(i < 0) {
			return Integer.MIN_VALUE;
		} else if(i > a.length-1) {
			return Integer.MAX_VALUE;
		} else {
			return a[i];
		}
	}
}
